#define _CRT_SECURE_NO_WARNINGS 1

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
void AdjustDown(vector<pair<int, ListNode*>>& vp, int parent)
{
    int child = parent * 2 + 1;

    while (child < vp.size())
    {
        if (child + 1 < vp.size() && vp[child].first > vp[child + 1].first)
            child++;

        if (vp[parent].first > vp[child].first) swap(vp[parent], vp[child]);
        else break;
        parent = child;
        child = parent * 2 + 1;
    }
}

class Solution {
public:
    ListNode* mergeKLists(vector<ListNode*>& lists) {
        if (lists.size() == 0) return nullptr;
        int n = lists.size();
        vector<pair<int, ListNode*>> vp;
        for (int i = 0; i < n; i++)
            if (lists[i] != nullptr) vp.push_back({ lists[i]->val, lists[i] });
        for (int i = (n - 2) / 2; i >= 0; i--) AdjustDown(vp, i);

        ListNode* newhead = new ListNode(0);
        ListNode* pcur = newhead;
        int num = vp.size();
        while (vp.size())
        {
            ListNode* tmp = vp[0].second;
            if (tmp->next)
            {
                vp[0].first = tmp->next->val;
                vp[0].second = tmp->next;
                AdjustDown(vp, 0);
            }
            else
            {
                swap(vp[0], vp[num - 1]);
                num--;
                vp.pop_back();
                AdjustDown(vp, 0);
            }
            pcur->next = tmp;
            pcur = tmp;
        }

        return newhead->next;
    }
};

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* mergeKLists(vector<ListNode*>& lists) {
        return merge(lists, 0, lists.size() - 1);
    }

    ListNode* merge(vector<ListNode*>& list, int left, int right)
    {
        if (left > right) return nullptr;
        if (left == right) return list[left];

        int mid = (left + right) / 2;
        ListNode* l1 = merge(list, left, mid);
        ListNode* l2 = merge(list, mid + 1, right);

        return mergeTwoList(l1, l2);
    }

    ListNode* mergeTwoList(ListNode* l1, ListNode* l2)
    {
        ListNode* head = new ListNode;
        ListNode* pcur = head;

        while (l1 && l2)
        {
            if (l1->val < l2->val)
            {
                pcur->next = l1;
                pcur = l1;
                l1 = l1->next;
            }
            else
            {
                pcur->next = l2;
                pcur = l2;
                l2 = l2->next;
            }
        }
        if (l1) pcur->next = l1;
        if (l2) pcur->next = l2;

        pcur = head->next;
        delete head;
        return pcur;
    }
};